package com.wh.codedemon.datastructure;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[]{21, 4, 23, 15, 4, 3, 1, 563, 2};
        // 假设第一个有序,从第二个开始
        for (int i = 1; i < arr.length; i++) {
            int pre = i - 1;
            int current = arr[i];
            // 把当前插入的值跟前面的值去比较,直到找到合适的位置
            while (pre >= 0 && arr[pre] > current) {
                arr[pre + 1] = arr[pre];
                pre = pre - 1;
            }
            arr[pre + 1] = current;
        }

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
